闲话:这场居然因为queueforces unrated了,如果打了的话我应该出的了ABC
本场传送门:https://codeforces.com/contest/1372/
A. Omkar and Completion
题目大意:构造一个长度为的数列,使之满足任意两个数之和在数列里不存在。
分析:直接构造一个的数列就可以了。
B. Omkar and Last Class of Math
题目大意:给定一个整数,找到一组数对满足且最大。
数据范围:
分析:首先有两个变量,先消个元看一下:原式,由于不怎么熟悉,就换成比较熟悉的再看:原式=,发现下面这个满足差分形式,即,由于要使原式最大,故可以猜测一个结论:的取值是的最大约数,找出的最小质因子,就是最大的约数了。
不过到此实际上还没解决问题(会WA4),因为如果数是个质数,那么他压根就没有任何的质因子,所以还需要特殊处理一下。由于是一个质数,则任何小于的数与之互质,即,故原式=,答案显然是当是最小,输出即可。
代码:
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int primes[N],cnt,st[N];
void init()
{
for(int i = 2;i < N;++i)
{
if(!st[i]) primes[++cnt] = i;
for(int j = 1;j <= cnt && i * primes[j] < N;++j)
{
st[i * primes[j]] = 1;
if(i % primes[j] == 0) break;
}
}
}
int main()
{
init();
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
int ok = 0;
for(int i = 1;i <= cnt;++i)
{
if(n % primes[i] == 0)
{
printf("%d %d\n",n / primes[i],n - n / primes[i]);
ok = 1;
break;
}
}
if(!ok)
{
printf("%d %d\n",1,n - 1);
}
}
return 0;
}
C. Omkar and Baseball
题目大意:给定一个长度为的数列,且是一组排列数,现在规定一种操作:每次可以选取一个区间,把区间内的数随意换位置,如果换完之后每个位置上的数都与原来的数不同,则可以进行这个操作,把新的数全换上去,否则不可以执行。问最少要几次可以完成对原数列的排序。
数据范围:
分析:首先由于数据范围很大,所以说最多也就遍历一次。手玩几组数据之后,一个大概的想法就是:开头和结尾已经有序的部分,肯定不用管了,所以要管的就是中间的部分。而中间这个部分可以分成两种情况:一种是中间有没有出现一个已经是有序的数,和中间完全是乱序的。
先看后面一种,我们可以发现如果中间完全是乱序的,只需要次操作就可以解决问题了。
如果是前者,中间出现了一个有序的数,这时只需要额外再操作次就可以解决问题了,第一步先把所有的其他数排好,之前有序的跟身边的一个交换一下位置,第二次把上次有序的和他旁边那个数再交换一下。
至此可以发现这个题的答案只有三种:,贪心策略是正确的。直接去遍历一遍查中间是不是有已经有序的就行了。
代码:
using namespace std;
typedef long long ll;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
vector<int> a(n + 17),st(n + 17);
for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
int flag = 0,last = -1;
for(int i = 1;i <= n;++i)
{
if(a[i] != i)
{
if(flag == 0) flag = 1,last = i;
else if(flag == 1)
{
if(last == -1) last = i;
else if(last != i - 1) flag = 2;
if(flag != 2) last = i;
}
// cout << flag << " " << last << endl;
}
}
printf("%d\n",flag);
}
return 0;
}
D. Omkar and Circle
题目大意:给定一个长度为,是奇数的数列,这个数列呈环状。每次可以选择环上的一个数,把这个数和他相邻的两个数删掉,用他相邻的两个数代替他。问最后整个环能得到的最大值是多少。
数据范围:
注意答案爆
分析:首先的范围太大了,常规区间dp不可取。我们必须要有一个线性的做法。分析之后可以发现这个题最大的困难在于某个点的值更新依赖于两边,而两边的贡献难算且很可能超复杂度,所以这个题必须要先做一步转换,看能不能消掉这个问题。
进而我们可以发现这个题是包装过的:用旁边两个数代替他,等价于把他自己删去,然后剩下的所有的数的和就是答案。形式化的语言来说明这个题目就是:在环上删掉个不相邻的数,使最后剩下来的和最大。由于本题是一个环,所以我们先要想怎么拆环变数列:复制环成两倍是可以的,不过还有另外一种:先把和看做是断开的,就是他俩不能相连的情况算出第一个答案,那么还剩下一种情况:他俩相连应该是什么样的,这个问题之后再分析,因为他涉及到实际的题目情况,不过想到这里的时候基本可以敲定正确性了,往下做没什么问题。
在一个数列上做这个题的时候,如果暴力枚举有多少个数删去了转移肯定是不行的,还要找到一个可以快速计算出答案得性质:由于说整个数列长度是个奇数,从里面扣个数之后,会产生个空隙,那么一共剩下了个数,故一定有两个没有被删的数是相邻的,并且只有一个。于是我们可以枚举所有可能情况:即枚举所有位置,表示相邻的那两个数的右端点的下标是,然后发现如果我们根据奇偶性来做前缀和的话,这个信息是非常好统计的,就可以以的代价算出删去的数的和了。于是复杂度就成功降到了。
现在我们回过头来看一下之前的那个问题:缺少的第二个条件该怎么补充。缺少的那个情况就是和没有相邻的情况,于是可以把挪到的前面,再做一次答案的求解过程,就可以把这种情况加上了。
分析完了具体该怎么分类之后,说明一下这个题该怎么实现。
首先这道题其实是一个原题(到这里来的话),题目是atcoder的abc_162F题,链接:https://atcoder.jp/contests/abc162/tasks/abc162_f
定义为开始到依次选不相邻的数时的总和。
入口:,其余为0
递推:。
注意这个前缀和是隔了一位的,推式子的时候要注意其实际意义。
如果当前枚举的是个奇数的话,答案是:

如果当前枚举的是个偶数的话,答案是:

最后,不要忘了做出另外一个数组,再做一次。
当然,实际上数组可以不用做满所有的操作,具体情况可以自己思考一下。
代码:
using namespace std;
typedef long long ll;
const int N = 2e5+7,INF = 1e9+7;
int a[N],b[N];
int n;
ll f[N];
ll slove(int c[])
{
f[1] = c[1];
// for(int i = 1;i <= n;++i) cout << c[i] << " ";cout << endl;
for(int i = 2;i <= n;++i) f[i] = f[i - 2] + c[i];
ll res = 1e18;
for(int i = 2;i <= n;++i)
{
if(i % 2 == 0)
{
res = min(res,f[i - 2] + f[n] - f[i - 1]);
}
else
{
res = min(res,f[n - 1] - f[i - 1] + f[i - 2]);
}
}
return res;
}
int main()
{
scanf("%d",&n);
ll sum = 0;
for(int i = 1;i <= n;++i) scanf("%d",&a[i]),sum += a[i];
if(n == 1)
{
printf("%d",a[1]);
return 0;
}
ll res = 0;
res = max(res,sum - slove(a));
b[1] = a[n];
for(int i = 2;i <= n;++i) b[i] = a[i - 1];
// for(int i = 1;i <= n;++i) cout << b[i] << " ";cout << endl;
res = max(res,sum - slove(b));
printf("%lld",res);
return 0;
}